9558. Флаги

Флаг состоит из n вертикальных полос, каждая из которых может быть окрашена в белый, красный или синий цвет. При этом:

· Никакие две соседние полосы не имеют одинаковый цвет.

· Любая синяя полоса обязательно должна находиться между красной и белой полосами (в любом порядке).

Сколько существует способов раскрасить флаг из n полос?

Вход. Одно целое число n (1 ≤ n ≤ 10⁶) – количество полос на флаге.

Выход. Выведите количество способов раскрасить флаг из n полос. Ответ необходимо вывести по модулю 10⁹ + 7.

Пример входа	Пример выхода
3	4

РЕШЕНИЕ

числа Фибоначчи

Анализ алгоритма

Пусть:

· f_r(n) – количество способов раскрасить флаг из n полос, начав с красной полосы;

· f_w(n) – количество способов раскрасить флаг из n полос, начав с белой полосы;

Рассмотрим вычисление функции f_r(n):

· Если следующей за красной поставить белую полосу, то оставшийся флаг длины n – 1 можно раскрасить f_w(n – 1) способами;

· Если следующей за красной поставить синюю полосу, то за синей должна стоять белая полоса. После чего оставшийся флаг длины n – 2 можно раскрасить f_w(n – 2) способами;

Итак, имеем равенство:

f_r(n) = f_w(n – 1) + f_w(n – 2)

Аналогичными рассуждениями получаем:

f_w(n) = f_r(n – 1) + f_r(n – 2)

Начальные условия для первой рекуррентности очевидны:

· f_r(1) = 1: Флаг из одной полосы, начинающийся с красной, может быть раскрашен только одним способом – R.

· f_r(2) = 1: Если первая полоса красная, то вторая не может быть красной и не может быть синей (синяя должна находиться между красной и белой), следовательно, вторая полоса обязана быть белой. Единственный вариант – RW.

Аналогично

f_w(1) = 1, f_w(2) = 1

Обе функции – и f_r(n) и f_w(n) задают числа Фибоначчи:

f_r(n) = F_n,

f_w(n) = F_n

Раскрашивание флага начинается с первой полосы. Она может быть либо красной, либо белой. Следовательно, общее количество способов раскрасить флаг равно

f_r(n) + f_w(n) = 2 * F_n

Реализация алгоритма

Объявим константы.

#define MAX 1000001

#define MOD 1000000007

Объявим массив fib для хранения чисел Фибоначчи.

long long fib[MAX];

Читаем входное значение n.

scanf("%d", &n);

Заполняем массив fib числами Фибоначчи.

fib[1] = 1; fib[2] = 1;

for (i = 3; i < MAX; i++)

fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;

Выводим ответ.

printf("%lld\n", (2 * fib[n]) % MOD);